package 中等.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为
 * intervals[i] = [starti, endi] 。请你合并所有重叠的
 * 区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输
 * 入中的所有区间 。
 */
public class 合并区间_56 {

    public static void main(String[] args) {

    }

    /**
     * 排序+双指针
     */
    public int[][] merge(int[][] intervals) {
        List<int[]> lists = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int left = 0;
        while (left < intervals.length) {
            int maxR = intervals[left][1];
            int right = left + 1;

            while (right < intervals.length &&
                    intervals[right][0] <= maxR) {
                // 注意右端点要取最大值
                maxR = Math.max(maxR, intervals[right][1]);
                right++;
            }
            lists.add(new int[]{intervals[left][0], maxR});

            left = right;
        }
        return lists.toArray(new int[lists.size()][2]);
    }

}
